package com.acyouzi.leetcode.dp;

/**
 * 17/9/26 14:34
 *
 * @author sunxu
 */
public class OnesandZeroes {
  public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m+1][n+1];
    for (String str : strs){
      int[] count = getCount(str);
      // 为什么要倒着，为了不让本次循环中前面的影响后面的
      // dp 中，如果需要用到上次循环前面的值就倒着循环，如果需要用到上次循环后面的值就正着循环
      for (int i = m; i >= count[0]; i--) {
        for (int j = n; j >= count[1]; j--) {
          dp[i][j] = Math.max(dp[i][j], dp[i-count[0]][j-count[1]]+1);
        }
      }
    }
    return dp[m][n];
  }
  private int[] getCount(String str) {
    int[] res = new int[2];
    for (int i=0;i<str.length();i++)
      res[str.charAt(i) - '0']++;
    return res;
  }
}
